Edge-Colorings in Graphs

This page began as a bibliography, and this paragraph may be replaced over time by a Synopsis of the topic.

ALSPACH, Brian and EL-ZANATI, Saad, [no date]. Beating The Odds. Invited Talks. pdf [Accessed 10 January 2024].

For many, many years some people have invested considerable effort in trying to get the best of casinos and other entities running gambling operations. In this talk, I’ll present a light-hearted coverage of some of the schemes that have been employed.

ANDREWS, Eric, LUMDUANHOM, Chira, LAFORGE, Elliot and ZHANG, Ping, 2016. On proper-path colorings in graphs. 2016. page [Accessed 10 January 2024].

Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u - v path of length d(u, v), then P is a proper u - v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u - v path in G and c is a strong proper coloring if every two vertices u and v are connected by a proper u - v geodesic in G. The minimum number of colors used a proper-path coloring and strong proper coloring of G are called the proper connection number pc(G) and strong proper connection number spc(G) of G, respectively. These concepts are inspired by the concepts of rainbow coloring, rainbow connection number rc(G), strong rainbow coloring and strong connection number src(G) of a connected graph G. The numbers pc(G) and spc(G) are determined for several well-known classes of graphs G. We investigate the relationship among these four edge colorings as well as the well-studied proper edge colorings in graphs. Furthermore, several realization theorems are established for the five edge coloring parameters, namely pc(G), spc(G), rc(G), src(G) and the chromatic index of a connected graph G.

BEHTOEI, Ali, 2012. The Locating Chromatic Number of the Join of Graphs.. Online. 21 January 2012. arXiv. arXiv:1112.2357. Available from: http://arxiv.org/abs/1112.2357 [Accessed 10 January 2024]. Let $f$ be a proper $k$-coloring of a connected graph $G$ and $Pi=(V_1,V_2,...,V_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$, the color code of $v$ with respect to $Pi$ is defined to be the ordered $k$-tuple $c_{{}_Pi}(v):=(d(v,V_1),d(v,V_2),...,d(v,V_k)),$ where $d(v,V_i)=min{d(v,x)|xin V_i}, 1leq ileq k$. If distinct vertices have distinct color codes, then $f$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by $Cchi_{{}_L}(G)$. In this paper, we study the locating chromatic number of the join of graphs. We show that when $G_1$ and $G_2$ are two connected graphs with diameter at most two, then $Cchi_{{}_L}(G_1+G_2)=Cchi_{{}_L}(G_1)+Cchi_{{}_L}(G_2)$, where $G_1+G_2$ is the join of $G_1$ and $G_2$. Also, we determine the locating chromatic numbers of the join of paths, cycles and complete multipartite graphs. arXiv:1112.2357 [math] BEHTOEI, Ali and OMOOMI, Behnaz, 2011. On the locating chromatic number of Kneser graphs. Discrete applied mathematics. Online. 2011. Vol. 159, no. 18, p. 2214–2221. Available from: https://www.sciencedirect.com/science/article/pii/S0166218X11002769 [Accessed 10 January 2024]. BERRY, Randall and MODIANO, Eytan, 2005. Optimal transceiver scheduling in WDM/TDM networks. IEEE Journal on Selected Areas in Communications. Online. 2005. Vol. 23, no. 8, p. 1479–1495. Available from: https://ieeexplore.ieee.org/abstract/document/1490637/ [Accessed 10 January 2024]. CHARTRAND, Gary, SAENPHOLPHAT, Varaporn and ZHANG, Ping, 2005. Resolving edge colorings in graphs. Ars Combinatoria. 2005. Vol. 74, p. 33–48. DE WERRA, D., GLOVER, F. and SILVER, E.A., 1995. A chromatic scheduling model with costs. IIE Transactions. Online. April 1995. Vol. 27, no. 2, p. 181–189. DOI 10.1080/07408179508936730. [Accessed 10 January 2024]. DE WERRA, Dominique, 1974. A note on graph coloring. Revue française d’automatique informatique recherche opérationnelle. Informatique théorique. Online. 1974. Vol. 8, no. R1, p. 49–53. Available from: http://www.numdam.org/item/ITA_1974__8_1_49_0.pdf [Accessed 10 January 2024]. FENG, Lihua, CAO, Jianxiang, LIU, Weijun, DING, Shifeng and LIU, Henry, 2016. The spectral radius of edge chromatic critical graphs. Linear Algebra and its Applications. Online. 2016. Vol. 492, p. 78–88. Available from: https://www.sciencedirect.com/science/article/pii/S0024379515006825 [Accessed 10 January 2024]. GARCÍA PALOMO, Miguel, 2022. Latin Polytopes and Their Applications. Online. PhD Thesis. Telecomunicacion. Available from: https://oa.upm.es/id/eprint/70082 [Accessed 10 January 2024]. HAKIMI, S. Louis and SCHMEICHEL, Edward F., 1999. Improved bounds for the chromatic index of graphs and multigraphs. Journal of Graph Theory. Online. December 1999. Vol. 32, no. 4, p. 311–326. DOI 10.1002/(SICI)1097-0118(199912)32:4<311::AID-JGT1>3.0.CO;2-X. [Accessed 10 January 2024]. JANUARIO, Tiago, URRUTIA, Sebastián, RIBEIRO, Celso C. and DE WERRA, Dominique, 2016. Edge coloring: A natural model for sports scheduling. European Journal of Operational Research. Online. 2016. Vol. 254, no. 1, p. 1–8. Available from: https://www.sciencedirect.com/science/article/pii/S0377221716301667 [Accessed 10 January 2024]. JOHNSTON, Daniel, 2015. Edge colorings of graphs and their applications. . Online. 2015. Available from: https://scholarworks.wmich.edu/dissertations/586/ [Accessed 10 January 2024]. KIRCHWEGER, Markus, PEITL, Tomáš and SZEIDER, Stefan, 2023. A SAT Solver’s Opinion on the Erdős-Faber-Lovász Conjecture. . Online. 2023. P. 17 pages, 788511 bytes. DOI 10.4230/LIPICS.SAT.2023.13. [Accessed 10 January 2024]. In 1972, Paul Erdős, Vance Faber, and Lászlo Lovász asked whether every linear hypergraph with n vertices can be edge-colored with n colors, a statement that has come to be known as the EFL conjecture. Erdős himself considered the conjecture as one of his three favorite open problems, and offered increasing money prizes for its solution on several occasions. A proof of the conjecture was recently announced, for all but a finite number of hypergraphs. In this paper we look at some of the cases not covered by this proof. We use SAT solvers, and in particular the SAT Modulo Symmetries (SMS) framework, to generate non-colorable linear hypergraphs with a fixed number of vertices and hyperedges modulo isomorphisms. Since hypergraph colorability is NP-hard, we cannot directly express in a propositional formula that we want only non-colorable hypergraphs. Instead, we use one SAT (SMS) solver to generate candidate hypergraphs modulo isomorphisms, and another to reject them by finding a coloring. Each successive candidate is required to defeat all previous colorings, whereby we avoid having to generate and test all linear hypergraphs. Computational methods have previously been used to verify the EFL conjecture for small hypergraphs. We verify and extend these results to larger values and discuss challenges and directions. Ours is the first computational approach to the EFL conjecture that allows producing independently verifiable, DRAT proofs.

KÖRNER, János and SIMONYI, Gábor, [no date]. Mathematical Institute of HAS, 1364 Budapest, POB 127, Hungary. ⇒ Trifference

LAFORGE, Elliot, [no date]. On Proper-Path Colorings in Graphs. . Online. Available from: http://mcccc.sites.unlv.edu/28/abstracts/Laforge.pdf [Accessed 10 January 2024]. LAFORGE, Elliot, 2016. Chromatic connectivity of graphs. Online. Western Michigan University. Available from: https://search.proquest.com/openview/6d39897e878f769270977fb0987a1c7a/1?pq-origsite=gscholar&cbl=18750 [Accessed 10 January 2024]. LOUIS HAKIMI, S. and KARIV, Oded, 1986. A generalization of edge‐coloring in graphs. Journal of Graph Theory. Online. June 1986. Vol. 10, no. 2, p. 139–154. DOI 10.1002/jgt.3190100202. [Accessed 10 January 2024]. Abstract Bounds are given on the number of colors required to color the edges of a graph (multigraph) such that each color appears at each vertex v at most m (ν) times. The known results and proofs generalize in natural ways. Certain new edge‐coloring problems, which have no counterparts when m (ν) = 1 for all ν ϵ V , are studied. SAENPHOLPHAT, Varaporn and ZHANG, Ping, 2003. On resolving edge colorings in graphs. International Journal of Mathematics and Mathematical Sciences. Online. 2003. Vol. 2003, p. 2947–2959. Available from: https://downloads.hindawi.com/journals/ijmms/2003/204068.pdf [Accessed 10 January 2024]. SAENPHOLPHAT, Varaporn and ZHANG, Ping, 2004. Conditional resolvability in graphs: a survey. International journal of mathematics and mathematical sciences. Online. 2004. Vol. 2004, p. 1997–2017. Available from: https://www.hindawi.com/journals/ijmms/2004/247096/abs/ [Accessed 10 January 2024]. VARAPORN, Saenpholphat and PING, Zhang, [no date]. On resolving edge colorings in graphs. International Journal of Mathematics and Mathematical Sciences. Vol. 2003, no. 46, p. 2947–2959.