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 条
  • [1] COLORING DECOMPOSITIONS OF COMPLETE GEOMETRIC GRAPHS
    Huemer, C.
    Lara, D.
    Rubio-Montiel, C.
    ACTA MATHEMATICA HUNGARICA, 2019, 159 (02) : 429 - 446
  • [2] On-line coloring of geometric intersection graphs
    Erlebach, T
    Fiala, J
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 23 (02): : 243 - 255
  • [3] Scaling laws for maximum coloring of random geometric graphs
    Borst, Sem
    Bradonjic, Milan
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 427 - 437
  • [4] Rooted Complete Minors in Line Graphs with a Kempe Coloring
    Kriesell, Matthias
    Mohr, Samuel
    GRAPHS AND COMBINATORICS, 2019, 35 (02) : 551 - 557
  • [5] Rooted Complete Minors in Line Graphs with a Kempe Coloring
    Matthias Kriesell
    Samuel Mohr
    Graphs and Combinatorics, 2019, 35 : 551 - 557
  • [6] Partitions of complete geometric graphs into plane trees
    Bose, P
    Hurtado, F
    Rivera-Campo, E
    Wood, DR
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2006, 34 (02): : 116 - 125
  • [7] Packing plane spanning trees and paths in complete geometric graphs
    Aichholzer, Oswin
    Hackl, Thomas
    Korman, Matias
    van Kreveld, Marc
    Loffler, Maarten
    Pilz, Alexander
    Speckmann, Bettina
    Welzl, Emo
    INFORMATION PROCESSING LETTERS, 2017, 124 : 35 - 41
  • [8] Coloring Artemis graphs
    Leveque, Benjamin
    Maffray, Frederic
    Reed, Bruce
    Trotignon, Nicolas
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2234 - 2240
  • [9] Dominator coloring and CD coloring in almost cluster graphs ☆
    Banik, Aritra
    Kasthurirangan, Prahlad Narasimhan
    Raman, Venkatesh
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2025, 150
  • [10] Coloring Geometric Range Spaces
    Aloupis, Greg
    Cardinal, Jean
    Collette, Sebastien
    Langerman, Stefan
    Smorodinsky, Shakhar
    DISCRETE & COMPUTATIONAL GEOMETRY, 2009, 41 (02) : 348 - 362