From Edge-Coloring to Strong Edge-Coloring
| Autor: | Petru Valicov, Reza Naserasr, Gerard J. Chang, Shinya Fujita, N. Narayanan, Valentin Borozan, Nathann Cohen |
|---|---|
| Přispěvatelé: | Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences (MTA), National Center for Theoretical Sciences [Taiwan] (NCTS), National Taiwan University [Taiwan] (NTU), Department of Mathematics [Taiwan], Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Yokohama National University, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Valicov, Petru, Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Extremal combinatorics
Discrete mathematics Infinitary combinatorics Applied Mathematics 010102 general mathematics 0102 computer and information sciences [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Upper and lower bounds Theoretical Computer Science Vertex (geometry) Combinatorics Edge coloring [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] Computational Theory and Mathematics 010201 computation theory & mathematics Bipartite graph Discrete Mathematics and Combinatorics Geometry and Topology 0101 mathematics Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics The Electronic Journal of Combinatorics, Open Journal Systems, 2015, 22 (2), pp.P2.9 Scopus-Elsevier The Electronic Journal of Combinatorics, 2015, 22 (2), pp.P2.9 |
| ISSN: | 1077-8926 |
| Popis: | In this paper we study a generalization of both proper edge-coloring and strong edge-coloring: $k$-intersection edge-coloring, introduced by Muthu, Narayanan and Subramanian. In this coloring, the set $S(v)$ of colors used by edges incident to a vertex $v$ does not intersect $S(u)$ on more than $k$ colors when $u$ and $v$ are adjacent. We provide some sharp upper and lower bounds for $\chi'_{k\text{-int}}$ for several classes of graphs. For $l$-degenerate graphs we prove that $\chi'_{k\text{-int}}(G)\leq (l+1)\Delta -l(k-1)-1$. We improve this bound for subcubic graphs by showing that $\chi'_{2\text{-int}}(G)\leq 6$. We show that calculating $\chi'_{k\text{-int}}(K_n)$ for arbitrary values of $k$ and $n$ is related to some problems in combinatorial set theory and we provide bounds that are tight for infinitely many values of $n$. Furthermore, for complete bipartite graphs we prove that $\chi'_{k\text{-int}}(K_{n,m}) = \left\lceil \frac{mn}{k}\right\rceil$. Finally, we show that computing $\chi'_{k\text{-int}}(G)$ is NP-complete for every $k\geq 1$.An addendum was added to this paper on Jul 4, 2015. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|