Coloring decompositions of complete geometric graphs

被引:0
|
作者
C. Huemer
D. Lara
C. Rubio-Montiel
机构
[1] Universitat Politècnica de Catalunya,Departament de Matemàtiques
[2] Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional,Departamento de Computación
[3] Universidad Nacional Autónoma de México,División de Matemáticas e Ingeniería, FES Acatlán
[4] UMI LAFMIA 3175 CNRS at CINVESTAV-IPN,Department of Algebra
[5] Comenius University,undefined
来源
Acta Mathematica Hungarica | 2019年 / 159卷
关键词
geometric graph; coloring; geometric chromatic index;
D O I
暂无
中图分类号
学科分类号
摘要
A decomposition of a non-empty simple graph G is a pair [G,P] such that P is a set of non-empty induced subgraphs of G, and every edge of G belongs to exactly one subgraph in P. The chromatic index χ′([G,P])\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi'([G,P])$$\end{document} of a decomposition [G,P] is the smallest number k for which there exists a k-coloring of the elements of P in such a way that for every element of P all of its edges have the same color, and if two members of P share at least one vertex, then they have different colors. A long standing conjecture of Erdős–Faber–Lovász states that every decomposition [Kn,P]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[K_{n}, P]$$\end{document} of the complete graph 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} satisfies χ′([Kn,P])≤n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi'([K_{n}, P])\leq n$$\end{document}. In this paper we work with geometric graphs, and inspired by this formulation of the conjecture, we introduce the concept of chromatic index of a decomposition of the complete geometric graph. We present bounds for the chromatic index of several types of decompositions when the vertices of the graph are in general position. We also consider the particular case when the vertices are in convex position and present bounds for the chromatic index of a few types of decompositions.
引用
收藏
页码:429 / 446
页数:17
相关论文
共 50 条
  • [41] Coloring, location and domination of corona graphs
    Gonzalez Yero, Ismael
    Kuziak, Dorota
    Rondon Aguilar, Amauris
    AEQUATIONES MATHEMATICAE, 2013, 86 (1-2) : 1 - 21
  • [42] Subgraph-Avoiding Coloring of Graphs
    Shen, Jia
    JOURNAL OF GRAPH THEORY, 2010, 63 (04) : 300 - 310
  • [43] Packing coloring of generalized Sierpinski graphs
    Korze, Danilo
    Vesel, Aleksander
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2019, 21 (03)
  • [44] Injective coloring of subclasses of chordal graphs
    Panda, B. S.
    Ghosh, Rumki
    THEORETICAL COMPUTER SCIENCE, 2025, 1023
  • [45] Clique coloring of dense random graphs
    Alon, Noga
    Krivelevich, Michael
    JOURNAL OF GRAPH THEORY, 2018, 88 (03) : 428 - 433
  • [46] Distinguishing geometric graphs
    Albertson, Michael O.
    Boutin, Debra L.
    JOURNAL OF GRAPH THEORY, 2006, 53 (02) : 135 - 150
  • [47] Differences between the list-coloring and DP-coloring for planar graphs
    Abe, Toshiki
    DISCRETE MATHEMATICS, 2021, 344 (08)
  • [48] Posets of geometric graphs
    Boutin, Debra L.
    Cockburn, Sally
    Dean, Alice M.
    Margea, Andrei M.
    ARS MATHEMATICA CONTEMPORANEA, 2012, 5 (02) : 269 - 288
  • [49] Five-coloring graphs on the Klein bottle
    Chenette, Nathan
    Postle, Luke
    Streib, Noah
    Thomas, Robin
    Yerger, Carl
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (05) : 1067 - 1098
  • [50] Acyclic coloring of graphs with some girth restriction
    Cai, Jiansheng
    Feng, Binlu
    Yan, Guiying
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (04) : 1399 - 1404