Results 1 to 10 of about 35,279 (159)
Linear time recognition of P4-indifference graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has ...
Michel Habib +2 more
doaj +10 more sources
Packing triangles in low degree graphs and indifference graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard.
Gordana Manić, Yoshiko Wakabayashi
doaj +5 more sources
Decompositions for the edge colouring of reduced indifference graphs
Theoretical Computer Science, 2003 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Celina M.H. de Figueiredo +3 more
openalex +3 more sources
The total chromatic number of split-indifference graphs
Discrete Mathematics, 2012 AbstractThe total chromatic number of a graph G, χT(G), is the least number of colours sufficient to colour the vertices and edges of a graph such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC) states that every simple graph G has χT(G)≤Δ(G)+2, and it is a challenging open problem
C.N. Campos +3 more
openalex +3 more sources
Indifference orders and split-indifference graphs: thirty years of productive collaborative work
Cadernos do IME - Série Informática, 2022 This is an account of our years as students of Jayme Luiz Szwarcfiter, during the years 1990. Two articles perfectly represent our experience as students, young researchers, and young authors.
Celina M.H. de Figueiredo +2 more
openalex +2 more sources
Optimal greedy algorithms for indifference graphs
Computers & Mathematics with Applications, 1993 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
P. Looges, Stephan Olariu
openalex +6 more sources
A Theorem on Indifference Graphs
The PUMP Journal of Undergraduate Research, 2021 An indifference graph P has as vertices a set of points on the real line, with an edge between every two points at most 1 apart. For every point x in P, we set N(x) to be the set of points that are adjacent to x. Fix an indifference graph P, and a positive integer k. Suppose that for every x in P, k divides |N(x)|.
Kieran Hilmer +2 more
openalex +3 more sources
Discrete Mathematics, 1982 AbstractLet G be a graph on v labelled vertices with E edges, without loops or multiple edges. Let v → ∞ and let E=E(v) be a function of v such that lim E(v)v23=c. The limit of the probability that a random graph is a unit interval graph, indifference graph or proper interval graph is exp(−43c3).
Joel E. Cohen
openalex +3 more sources
On edge-colouring indifference graphs
Theoretical Computer Science, 1995 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Celina M.H. de Figueiredo +2 more
openalex +2 more sources
Block-indifference graphs: Characterization, structural and spectral properties
Discrete Applied Mathematics, 2018 Abstract We present a characterization of graphs which are simultaneously block and indifference graphs. Some structural and spectral properties of the class are depicted and their interconnection is shown. We show an O ( n ) representation which allows us to count the number of elements of the class.
Nair Maria Maia de Abreu +4 more
openalex +3 more sources