2004, OXFORD LECTURE SERIES IN MATHEMATICS AND ITS APPLICATIONS; 28., ISBN 9780198528173, Volume 28, 257

Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is...

Homomorphisms (Mathematics) | Graph theory

Homomorphisms (Mathematics) | Graph theory

Book

Computer Science Review, ISSN 1574-0137, 2008, Volume 2, Issue 3, pp. 143 - 163

Constraint satisfaction problems have enjoyed much attention since the early seventies, and in the last decade have become also a focus of attention amongst...

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 01/2017, Volume 216, pp. 211 - 232

Let Pt and Cℓ denote a path on t vertices and a cycle on ℓ vertices, respectively. In this paper we study the k-coloring problem for (Pt,Cℓ)-free graphs. Bruce...

Coloring | Obstructions | NP-complete | Paths and cycles | Certifying algorithms | NP-COMPLETENESS | MATHEMATICS, APPLIED | 3-COLORABILITY | Online searching | Internet/Web search services | Algorithms | Database searching

Coloring | Obstructions | NP-complete | Paths and cycles | Certifying algorithms | NP-COMPLETENESS | MATHEMATICS, APPLIED | 3-COLORABILITY | Online searching | Internet/Web search services | Algorithms | Database searching

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 05/2019, Volume 261, pp. 219 - 228

A graph is a cograph if it is P4-free. A k-polar partition of a graph G is a partition of the set of vertices of H into parts A and B such that the subgraph...

Matrix partition | Forbidden subgraph characterization | Generalized coloring | Polar graph | Cograph | [formula omitted]-polar graph | k-polar graph | MATHEMATICS, APPLIED | Computer science | Graphs | Polarity | Obstructions | Partitions | Graph theory | Apexes

Matrix partition | Forbidden subgraph characterization | Generalized coloring | Polar graph | Cograph | [formula omitted]-polar graph | k-polar graph | MATHEMATICS, APPLIED | Computer science | Graphs | Polarity | Obstructions | Partitions | Graph theory | Apexes

Journal Article

1978, Annals of discrete mathematics, ISBN 9780720410433, Volume 2, vii, 245

Book

1991, KAM series, discrete mathematics and combinatorics, operations research, mathematical linguistics, Volume no. 196., 12, [2]

Book

Discrete Applied Mathematics, ISSN 0166-218X, 07/2020, Volume 281, pp. 235 - 245

Journal Article

Theoretical Computer Science, ISSN 0304-3975, 06/2015, Volume 584, pp. 53 - 66

We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model,...

Influence diffusion | Target set selection | MONOPOLIES | COMPUTER SCIENCE, THEORY & METHODS | MODEL | GRAPHS | Computer science | Social networks | Algorithms | Windows (intervals) | Networks | Approximation | Mathematical models | Polynomials | Combinatorial analysis | Rings (mathematics)

Influence diffusion | Target set selection | MONOPOLIES | COMPUTER SCIENCE, THEORY & METHODS | MODEL | GRAPHS | Computer science | Social networks | Algorithms | Windows (intervals) | Networks | Approximation | Mathematical models | Polynomials | Combinatorial analysis | Rings (mathematics)

Journal Article

SIAM Journal on Discrete Mathematics, ISSN 0895-4801, 2012, Volume 26, Issue 4, pp. 1597 - 1608

The minimum cost homomorphism problem has arisen as a natural and useful optimization problem in the study of graph (and digraph) coloring and homomorphisms:...

Dichotomy | Min-Max orderings | Minimum cost homomorphisms | CONSTRAINT SATISFACTION | MATHEMATICS, APPLIED | TREES | dichotomy | CSP DICHOTOMY | COMPLEXITY | minimum cost homomorphisms

Dichotomy | Min-Max orderings | Minimum cost homomorphisms | CONSTRAINT SATISFACTION | MATHEMATICS, APPLIED | TREES | dichotomy | CSP DICHOTOMY | COMPLEXITY | minimum cost homomorphisms

Journal Article

Discussiones Mathematicae Graph Theory, ISSN 2083-5892, 02/2014, Volume 34, Issue 1, pp. 167 - 185

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u,...

3-kernel | k-quasi-transitive digraph | multipartite tournament | cyclically 3-partite digraphs | kernel | NP-completeness | Multipartite tournament | Kernel | K-quasi-transitive digraph | Cyclically 3-partite digraphs | MATHEMATICS | QUASI-TRANSITIVE DIGRAPHS | KERNELS

3-kernel | k-quasi-transitive digraph | multipartite tournament | cyclically 3-partite digraphs | kernel | NP-completeness | Multipartite tournament | Kernel | K-quasi-transitive digraph | Cyclically 3-partite digraphs | MATHEMATICS | QUASI-TRANSITIVE DIGRAPHS | KERNELS

Journal Article

SIAM Journal on Discrete Mathematics, ISSN 0895-4801, 2012, Volume 26, Issue 4, pp. 1576 - 1596

We introduce a class of digraphs analogous to proper interval graphs and bigraphs. They are defined via a geometric representation by two inclusion-free...

Min-Max orderings | Minimum cost homomorphisms | Forbidden structure characterizations | Interval digraphs | forbidden structure characterizations | CHROMATIC PARTITION PROBLEM | MATHEMATICS, APPLIED | LIST HOMOMORPHISMS | TREES | MINIMUM-COST HOMOMORPHISMS | RECOGNITION | interval digraphs | minimum cost homomorphisms | DICHOTOMY | GRAPHS

Min-Max orderings | Minimum cost homomorphisms | Forbidden structure characterizations | Interval digraphs | forbidden structure characterizations | CHROMATIC PARTITION PROBLEM | MATHEMATICS, APPLIED | LIST HOMOMORPHISMS | TREES | MINIMUM-COST HOMOMORPHISMS | RECOGNITION | interval digraphs | minimum cost homomorphisms | DICHOTOMY | GRAPHS

Journal Article

Discrete Mathematics, ISSN 0012-365X, 02/2017, Volume 340, Issue 2, pp. 223 - 235

We study homomorphism problems of signed graphs from a computational point of view. A signed graph (G,Σ) is a graph G where each edge is given a sign, positive...

Graph homomorphism | Dichotomy theorem | Signed graph | Edge-coloured graph | MATHEMATICS | LIST HOMOMORPHISMS | ARC GRAPHS

Graph homomorphism | Dichotomy theorem | Signed graph | Edge-coloured graph | MATHEMATICS | LIST HOMOMORPHISMS | ARC GRAPHS

Journal Article

2014, Lecture Notes in Computer Science, ISBN 9783319079554, Volume 8546, 355

eBook

Mathematical Programming, ISSN 0025-5610, 2/2006, Volume 105, Issue 2, pp. 201 - 213

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a...

Asteroidal triple-free graph | Mathematical and Computational Physics | Circular-arc graph | Chordal graph | Interval-filament graph | Mathematics | Optimization | Weakly chordal graph | Cocomparability graph | Mathematical Methods in Physics | 20G40 | Induced matching | 20C20 | Mathematics of Computing | Numerical Analysis | Dissociation set | Calculus of Variations and Optimal Control | Independent set | Chordal bipartite graph | 20E28 | Combinatorics | Intersection graph | Polygon-circle graph | circular-arc graph | MATHEMATICS, APPLIED | asteroidal triple-free graph | COMPARABILITY-GRAPHS | weakly chordal graph | chordal graph | independent set | induced matching | COMPUTER SCIENCE, SOFTWARE ENGINEERING | OPERATIONS RESEARCH & MANAGEMENT SCIENCE | MAXIMUM INDUCED MATCHINGS | polygon-circle graph | cocomparability graph | chordal bipartite graph | PARALLEL ALGORITHMS | SETS | interval-filament graph | dissociation set | intersection graph | Studies | Mathematical models | Polynomials | Algorithms | Theory | Mathematical programming

Asteroidal triple-free graph | Mathematical and Computational Physics | Circular-arc graph | Chordal graph | Interval-filament graph | Mathematics | Optimization | Weakly chordal graph | Cocomparability graph | Mathematical Methods in Physics | 20G40 | Induced matching | 20C20 | Mathematics of Computing | Numerical Analysis | Dissociation set | Calculus of Variations and Optimal Control | Independent set | Chordal bipartite graph | 20E28 | Combinatorics | Intersection graph | Polygon-circle graph | circular-arc graph | MATHEMATICS, APPLIED | asteroidal triple-free graph | COMPARABILITY-GRAPHS | weakly chordal graph | chordal graph | independent set | induced matching | COMPUTER SCIENCE, SOFTWARE ENGINEERING | OPERATIONS RESEARCH & MANAGEMENT SCIENCE | MAXIMUM INDUCED MATCHINGS | polygon-circle graph | cocomparability graph | chordal bipartite graph | PARALLEL ALGORITHMS | SETS | interval-filament graph | dissociation set | intersection graph | Studies | Mathematical models | Polynomials | Algorithms | Theory | Mathematical programming

Journal Article

Discrete Mathematics, ISSN 0012-365X, 12/2015, Volume 338, Issue 12, pp. 2453 - 2461

We consider certain partition problems typified by the following two questions. When is a given graph the join of two k-colourable graphs? When is a given...

Graph homomorphism | Chordal graph | Split graph | Graph partition | Forbidden subgraph characterization | MATHEMATICS | OBSTRUCTIONS | MATRIX PARTITIONS | Partitions | Obstructions | Algorithms | Mathematical analysis | Graphs | Colouring | Complement | Recognition

Graph homomorphism | Chordal graph | Split graph | Graph partition | Forbidden subgraph characterization | MATHEMATICS | OBSTRUCTIONS | MATRIX PARTITIONS | Partitions | Obstructions | Algorithms | Mathematical analysis | Graphs | Colouring | Complement | Recognition

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 10/2017, Volume 229, pp. 64 - 81

A tropical graph (H,c) consists of a graph H and a (not necessarily proper) vertex-colouring c of H. Given two tropical graphs (G,c1) and (H,c), a homomorphism...

Dichotomy | Graph homomorphisms | Tropical graphs | CONSTRAINT SATISFACTION PROBLEMS | MATHEMATICS, APPLIED | LIST HOMOMORPHISMS | ARC GRAPHS | CYCLES | Mathematics | Computer Science

Dichotomy | Graph homomorphisms | Tropical graphs | CONSTRAINT SATISFACTION PROBLEMS | MATHEMATICS, APPLIED | LIST HOMOMORPHISMS | ARC GRAPHS | CYCLES | Mathematics | Computer Science

Journal Article

No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.