On the Pseudoachromatic Index of the Complete Graph III

被引:0
作者
M. Gabriela Araujo-Pardo
Juan José Montellano-Ballesteros
Christian Rubio-Montiel
Ricardo Strausz
机构
[1] Universidad Nacional Autónoma de México,Instituto de Matemáticas
[2] Universidad Nacional Autónoma de México,División de Matemáticas e Ingeniería, FES Acatlán
[3] UMI LAFMIA 3175 CNRS at CINVESTAV-IPN,undefined
来源
Graphs and Combinatorics | 2018年 / 34卷
关键词
Finite projective plane; Complete colourings; Complete edge-colouring; Pseudoachromatic index; Complete graph; 05C15; 51E15;
D O I
暂无
中图分类号
学科分类号
摘要
An edge colouring of a graph G is complete if for any distinct colours c1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_1$$\end{document} and c2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_2$$\end{document} one can find in G adjacent edges coloured with c1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_1$$\end{document} and c2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_2$$\end{document}, respectively. The pseudoachromatic index of G is the maximum number of colours in a complete edge colouring of G. Let ψ(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\psi (n)$$\end{document} denote the pseudoachromatic index of Kn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_n$$\end{document}. In the paper we proved that if x≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ x\ge 2 $$\end{document} is an integer and n∈{4x2-x,⋯,4x2+3x-3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\in \{4x^2-x,\dots ,4x^2+3x-3\}$$\end{document}, then ψ(n)≤2x(n-x-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\psi (n) \le 2x(n-x-1)$$\end{document}. Let q be an even integer and let ma=(q+1)2-a\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ m_a=(q+1)^2-a $$\end{document}. If there is a projective plane of order q, a complete edge colouring of Kma\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{m_a}$$\end{document} with (ma-a)q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(m_a-a)q$$\end{document} colours, a∈{-1,0,⋯,q2+1}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ a\in \{-1,0,\dots ,\frac{q}{2}+1\}$$\end{document}, is presented. The main result states that if q≥4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q\ge 4$$\end{document} is an integer power of 2, then ψ(ma)=(ma-a)q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\psi (m_a)=(m_a-a)q$$\end{document} for any a∈{-1,0,⋯,1+4q+92-1}.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ a\in \{-1,0,\dots ,\left\lceil \frac{1+\sqrt{4q+9}}{2}\right\rceil -1 \} .$$\end{document}
引用
收藏
页码:277 / 287
页数:10
相关论文
共 22 条
  • [1] Araujo-Pardo G(2011)On the pseudoachromatic index of the complete graph J. Graph Theory 66 89-97
  • [2] Montellano-Ballesteros JJ(2014)On the pseudoachromatic index of the complete graph II Bol. Soc. Mat. Mex. 20 17-28
  • [3] Strausz R(1976)Complete and pseudocomplete colourings of a graph Math. Slovaca 26 171-184
  • [4] Araujo-Pardo G(1978)Indice achromatique des graphes multiparti complets et réguliers Cahiers Centre Études Rech. Opér. 20 331-340
  • [5] Montellano-Ballesteros JJ(1974)Further results on the achromatic number Fund. Math. 85 285-290
  • [6] Rubio-Montiel C(1997)Achromatic index of $K_{12}$ Ars. Comb. 45 271-275
  • [7] Strausz R(2004)On the achromatic index of $K_{q^2+q}$ for a prime $q$ Graphs Comb. 20 191-203
  • [8] Bosák J(1989)On the edge achromatic number of complete graphs Discrete Math. 74 99-115
  • [9] Nešetřil J(1991)On the achromatic index of $K_{12}$ Congr. Numer. 81 143-148
  • [10] Bouchet A(1988)The edge achromatic number of small complete graphs Congr. Numer. 62 21-36