Bujtás, Csilla and Sampathkumar, E. and Tuza, Zsolt and Dominic, C. and Pushpalatha, L (2016) When the vertex coloring of a graph is an edge coloring of its line graph  a rare coincidence. ARS COMBINATORIA, 128. pp. 165173. ISSN 03817032

Text
3c_edgvert_R_u.pdf Download (180kB)  Preview 
Abstract
The 3consecutive vertex coloring number psi(3c)(G) of a graph G is the maximum number of colors permitted in a coloring of the vertices of G such that the middle vertex of any path P3 subset of G has the same color as one of the ends of that P3. This coloring constraint exactly means that no P3 subgraph of G is properly colored in the classical sense. The 3consecutive edge coloring number psi(3c)'(G) is the maximum number of colors permitted in a coloring of the edges of G such that the middle edge of any sequence of three edges (in a path P4 or cycle C3) has the same color as one of the other two edges. For graphs G of minimum degree at least 2, denoting by L(G) the line graph of G, we prove that there is a bijection between the 3consecutive vertex colorings of G and the 3consecutive edge colorings of L(G), which keeps the number of colors unchanged, too. This implies that psi(3c)(G) = psi(3c)'(L(G)); i.e., the situation is just the opposite of what one would expect for first sight.
Item Type:  Article 

Uncontrolled Keywords:  STABLE CUTSETS; Stable kseparator; Matching; Line graph; 3consecutive edge coloring; 3consecutive vertex coloring 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  04 Jan 2017 10:48 
Last Modified:  04 Jan 2017 10:48 
URI:  http://real.mtak.hu/id/eprint/44501 
Actions (login required)
Edit Item 